package List;

import java.util.List;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/28 15:02
 * @description: 力扣141 使用插入排序方式 排序单链表
 * 思路：
 * 变量 Listnode Lastsorted 变量维持一个已排序的最后一个链表节点
 * 变量 Listnode curr = Lastsorted.next 变量维持一个当前需要插入排序的节点
 * 变量 Listnode pre是当前curr需要插入到的节点的前节点
 */

class Listnode {
    int val;
    Listnode next;

    Listnode(int val) {
        this.val = val;
    }

    Listnode(int val, Listnode next) {
        this.val = val;
        this.next = next;
    }
}
public class SortList {
}
class SortList_Solution{
    public Listnode sortList1(Listnode head){
        if(head == null){
            return null;
        }
        Listnode Lastersorted = head;
        Listnode curr = head.next;
        Listnode dummyHead = new Listnode(0);
        dummyHead.next = head;
        while (curr!=null){
            if(curr.val >= Lastersorted.val){
                Lastersorted = curr;
            }
            else {
                Listnode pre = dummyHead;
                while (pre.next.val <= curr.val){
                    pre = pre.next;
                }
                Lastersorted.next = curr.next;
                curr.next = pre.next;
                pre.next = curr;
            }
            curr = Lastersorted.next;
        }
        return dummyHead.next;  //重点：配合第46开始看，dummyHead.next是会变化的
    }
}
